package heap;


public class HeapSort {

	public static void main(String[] args) {
		int[] arr1 ={4,7,4,1,0,10,-1};
		heapSort(arr1);
		print(arr1);
	}
	
	private static void print(int[] arr){
		for(int num: arr){
			System.out.print(num);
			System.out.print(", ");
		}
		System.out.print("\r\n ");
	}
	
	public static void heapSort(int[] arr){
		heapify(arr);
		int end = arr.length -1;
		while(end>0){
			swap(arr, 0, end);
			end--;
			sink(arr, 0, end);
		}
		
	}
	
	private static void heapify(int[] arr){
		for(int i= arr.length/2 - 1;i>=0;i--){
			sink(arr, i, arr.length - 1);
		}
	}
	
	private static void sink(int[] arr, int begin, int end){
		int root = begin, largest = root;
		if(2*root+1<=end && arr[root]<arr[2*root+1]){
			largest = 2*root+1;
		}
		if(2*root+2<=end && arr[largest]<arr[2*root+2]){
			largest = 2*root+2;
		}
		if(root!=largest){
			swap(arr, root, largest);
			sink(arr, largest, end);
		}
	}
	
	private static void swap(int[]arr, int i, int j){
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
		
	}

}
